package com.leetcode.union_find;

/**
 * @author Dennis Li
 * @date 2020/9/7 17:26
 */
public class Friends_547 {

    private int[] friends;

    public int find(int i) {
        return friends[i] == i ? i : (friends[i] = find(friends[i]));
    }

    public void union(int x, int y) {
        int f1 = find(x);
        int f2 = find(y);
        if (f1 != f2) {
            friends[f2] = f1;
            count--;
        }
    }

    int count;

    public int findCircleNum(int[][] M) {
        final int length = M.length;
        friends = new int[length];
        count = length;
        for (int i = 0; i < length; i++) {
            friends[i] = i;
        }

        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                if (M[i][j] == 1) {
                    union(i, j);
                }
            }
        }

        return count;
    }

    public static void main(String[] args) {
        final Friends_547 friends = new Friends_547();
        int[][] M = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}};
        final int circleNum = friends.findCircleNum(M);
        System.out.println(circleNum);
    }

}
